#pragma once
#include<iostream>
#include<bitset>
#include<vector>
#include<string>
#include <chrono>
#include <random>
#include <fstream>
#include <algorithm>
using namespace std;
using namespace std::chrono;

class BKDRHash 
{
public:
    size_t operator()(const string& str) 
    {
        size_t hash = 0;
        for (char ch : str) 
        {
            hash = hash * 131 + static_cast<size_t>(ch);
        }
        return hash;
    }
};

class APHash {
public:
    size_t operator()(const string& str) 
    {
        size_t hash = 0;
        for (long i = 0; i < str.size(); i++) 
        {
            size_t ch = static_cast<size_t>(str[i]);
            if ((i & 1) == 0) 
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else 
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

class JSHash 
{
public:
    size_t operator()(const string& str) 
    {
        if (str.empty()) return 0;
        size_t hash = 1315423911;
        for (char ch : str) 
        {
            hash ^= ((hash << 5) + static_cast<size_t>(ch) + (hash >> 2));
        }
        return hash;
    }
};

class DJBHash 
{
public:
    size_t operator()(const string& str) 
    {
        if (str.empty()) return 0;
        size_t hash = 5381;
        for (char ch : str) 
        {
            hash += (hash << 5) + static_cast<size_t>(ch);
        }
        return hash;
    }
};


template<size_t N,class k = string,
	class BKDRHash = BKDRHash,
	class APHash = APHash,
	class DJBHash = DJBHash,
	class JSHash = JSHash>
class BloomFilter
{
public:
    void set(k& key)
    {
        size_t hashi1 = BKDRHash()(key) % N;
        _bitmap.set(hashi1);
        
        size_t hashi2= APHash()(key) % N;
        _bitmap.set(hashi2);

        size_t hashi3 = DJBHash()(key) % N;
        _bitmap.set(hashi3);

        size_t hashi4 = JSHash()(key) % N;
        _bitmap.set(hashi4);
    }

    bool test(k key)
    {
        size_t hashi1 = BKDRHash()(key) % N;
        size_t hashi2 = APHash()(key) % N;
        size_t hashi3 = DJBHash()(key) % N;
        size_t hashi4 = JSHash()(key) % N;
        
        return _bitmap.test(hashi1) && _bitmap.test(hashi2) && _bitmap.test(hashi3) && _bitmap.test(hashi4);
    }

private:
	bitset<N> _bitmap;
};

